/*
 * @Author: 缄默
 * @Date: 2021-11-10 18:48:58
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-10 19:24:41
 */
#include <iostream>
#include <vector>
#include <map>
#include "../../DataStructure/tree.hpp"

using namespace std;

bool isBSTNode(TreeNode* h, TreeNode* n);
int bstTopoSize1(TreeNode* head);
int maxTopo(TreeNode* h, TreeNode* n);

int main() {
    vector<int> preOrder({6, 1, 0, 3, 12, 10, 4, 2, 5, 14, 11, 15, 13, 20, 16});
    vector<int> inOrder({0, 1, 3, 6, 2, 4, 5, 10, 11, 14, 15, 12, 20, 13, 16});
    TreeNode* head = buildTree(preOrder, inOrder, 0, 0, preOrder.size() - 1);
    cout << bstTopoSize1(head) << endl;
    return 0;
}

//求出当前节点的最大值以及左右子树的最大值  遍历比较每一个节点为根节点的最大拓扑结构
int bstTopoSize1(TreeNode* head) {
    if (head == nullptr) return 0;
    int max = maxTopo(head, head);
    int left = bstTopoSize1(head->left);
    int right = bstTopoSize1(head->right);
    max = left < max ? max : left;
    max = right < max ? max : right;
    return max;
}

//以当前节点为根节点的最大拓扑结构
int maxTopo(TreeNode* h, TreeNode* n) {
    //判断是否可以在当前h节点的子树上找到n节点
    if (h != nullptr && n != nullptr && isBSTNode(h, n)) {
        //找到左右节点的最大拓扑结构的节点数量
        return maxTopo(h, n->left) + maxTopo(h, n->right) + 1;
    }
    return 0;
}

//判断是否可以在当前h节点的子树上找到n节点
bool isBSTNode(TreeNode* h, TreeNode* n) {
    if (h == nullptr) return false;
    if (h == n) return true;
    //判断递归搜索的是左子树还是右子树
    return isBSTNode(h->val > n->val ? h->left : h->right, n);
}
